\documentclass[E:/GsjzTle/main/main.tex]{subfiles}

\begin{document}

\begin{itemize}
\item
  转换为 \(01\) 背包：（暴力拆解）\\
  比如物品 \(A\) 有 \(k\) 个，我们不妨将它拆解为 \(k\) 个新物品，这
  \(k\) 个新物品的体积为价值都和物品 \(A\) 相同，那么这就转换为了 \(01\)
  背包问题
\item
  转换为 \(01\) 背包：（二进制优化拆解）\\
  比如物品 \(A\) 有 \(k\) 个，物品 \(A\) 的体积为 \(w\)，价值为 \(v\) \\
  我们不妨将它拆解为 ：\\
  \(1\) 个体积为 \(w\) ，价值为 \(v\) 的物品\\
  \(1\) 个体积为 \(2w\)，价值为 \(2v\) 的物品\\
  \(1\) 个体积为 \(4w\)，价值为 \(4v\) 的物品\\
  \(1\) 个体积为 \(8w\)，价值为 \(8v\) 的物品\\
  ......

  \(1\) 个体积为 \(2^xw\)，价值为 \(2^xw\) 的物品\\
  \(1\) 个体积为 \((k - (1 + 2 + 4 + ...+2^x)) \times w\) ，价值为
  \((k - (1+2+4+...2^x)) \times v\) 的物品\\
  当 \(2^0+2^1+...+2^{x+1}>k\) 时停止拆解，拆解的最后一个物品的系数等于
  \(k - 2^0+...+2^x\)
\item
  单调队列优化\\
  \(qwq\) 见代码
\item
  二、

\begin{lstlisting}
int dp[M];
int n , v[M << 1] , w[M << 1];
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0) , cout.tie(0);
	int n , V , cnt = 0;
	cin >> n >> V;
	for(int i = 1 ; i <= n ; i ++)
	{
		int ww , vv , S;
		cin >> ww >> vv >> S;
		int b = 0;
		while(S >= (1 << b))
		{
			int x = (1 << b);
			w[++ cnt] = ww * x , v[cnt] = vv * x;
			S -= (1 << b);
			b ++ ;
		}
		if(S) w[++ cnt] = S * ww , v[cnt] = S * vv; 
	}
	for(int i = 1 ; i <= cnt ; i ++)
	{
		for(int j = V ; j >= w[i] ; j --) dp[j] = max(dp[j] , dp[j - w[i]] + v[i]);
	}
	cout << dp[V] << '\n';
	return 0;
}
\end{lstlisting}
\item
  三、
\end{itemize}

\begin{lstlisting}
#include <bits/stdc++.h>
using namespace std;
int n, m;
int f[20002], q[20002], g[20002];
int main()
{
	cin >> n >> m;
	for
	(int i = 1; i <= n; ++i)
	{
		int v, w, s;
		cin >> v >> w >> s;
		memcpy(g, f, sizeof(f));
		for (int j = 0; j < v; ++j)
		{
			/*
			hh为队首位置
			tt为队尾位置
			数值越大，表示位置越后面
			队首在队尾后面队列为空，即hh>tt时队列为空
			*/
			int hh = 0, tt = -1;
			/*
			q[]为单调队列
			存储前个s(物品数量)中的最大值
			数组从头(hh)到尾(tt)单调递减
			*/
			for (int k = j; k <= m; k += v)
			{

				// f[k] = g[k]; //这一行我没理解有什么用，去掉后也能ac？我认为前面使用过了memcpy,这里应该一定是相等的
				//k代表假设当前背包容量为k
				//q[hh]为队首元素（最大值的下标）
				//g[]为dp[i-1][]
				//f[]为dp[i][]
				/*
				维护一个大小为k的区间
				使最大值为前k个元素中最大
				(k - q[hh]) / v 表示拿取物品的数量（相当于最原始的多重背包dp的k）
				*/
				if (hh <= tt && (k - q[hh]) / v > s)
				{
					hh ++;
				}
				/*
				若队内有值，该值就是前k个元素的最大值
				(k - q[hh]) / v 表示拿取物品的数量（相当于最原始的多重背包dp的k）
				q[hh]为队首元素（g[]中前k个数中最大值的下标），g[]为dp[i-1][]
				所以 g[q[hh]]为只考虑前i-1个物品时，拿前q[hh]个物品的最大价值
				*/
				if (hh <= tt)
				{
					f[k] = max(f[k], g[q[hh]] + (k - q[hh]) / v * w);
				}
				/*
				若队尾元素小于当前元素，则队尾元素出队；
				若队内一个元素比当前元素小，则该元素一定不会被用到（单调队列思想）
				g[q[tt]] + (k - q[tt]) / v * w
				与
				g[k] - (k - j) / v * w
				分别表示队尾元素的值和当前元素的值
				*/
				while (hh <= tt && g[q[tt]] - (q[tt] - j) / v * w <= g[k] - (k - j) / v * w)
				{
					tt--;
				}
				q[++ tt] = k;
			}
		}
	}
	cout << f[m] << '\n';
	return 0;
}
\end{lstlisting}

\end{document}
